//
// Created by lxinp on 2022/8/10.
//

#ifndef DATASTRUCTURE_BINARY_TREE_H
#define DATASTRUCTURE_BINARY_TREE_H


template<typename T>
class BinaryTree {
public:
    BinaryTree();
    BinaryTree(const BinaryTree<T>& other);
    ~BinaryTree();
    BinaryTree<T>& operator=(const BinaryTree<T>& other);  // TODO: <T>? Why const?

    void clear();
    void insert(const T& data, bool sorted=true);
    int height() const;
    void print() const;
    void mirror();
    bool is_ordered() const;  // check if BST or in-order traversal
    void print_path() const;
    int sum_distances() const;

private:
    struct Node {
        T data;
        Node* left;
        Node* right;
        explicit Node(const T& data) : data(data), left(nullptr), right(nullptr) {}
    };
    Node* root;

    Node* copy(const Node* other);
    int height(const Node* subtree) const;
    void mirror(Node* subtree);
    bool is_ordered(const Node* subtree, const Node* left, const Node* right) const;
    void clear(Node* subtree);
    void insert(Node* subtree, const T& data, bool sorted=false);
};


#endif //DATASTRUCTURE_BINARY_TREE_H
